package com.example.sort;

/**
 * Created by Quincy on 2018/9/12.
 */
public class HeapSort {

    private HeapSort(){}

    public static void sort(Comparable[] arr){
        int n = arr.length;

        // 注意，此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1
        //这一步for循环，其实就是构建一个最大堆
        //i 值其实就是最后一个拥有叶子节点的节点index
        for (int i = (n-1-1)/2; i >= 0; i--)
            shiftDown(arr, n, i);
        //这一步for循环，则是不断取根节点的数，每次shiftDown操作只针对顶层三个顶点，即不断取最大值
        for (int i = n-1; i > 0; i--){
            swap(arr, 0, i); //将
            shiftDown(arr, i, 0);
        }
    }

    /**
     * 这里的shiftdown其实就是，判断根节点和两个子节点的大小，然后取最大值为根节点
     * */
    private static void shiftDown(Comparable[] arr, int n, int k){
        while (2*k + 1 < n){
            int j = 2*k + 1;
            if ( j + 1 < n && arr[j+1].compareTo(arr[j]) > 0)
                j += 1;
            if (arr[k].compareTo(arr[j]) >= 0) break;
            swap(arr, k, j);
            k = j;
        }
    }

    // 交换堆中索引为i和j的两个元素
    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


}
